#@TIME :2018/6/28 14:41
#@Author:Wyndem
#@File:chapter_8.py
'贪心算法'

# 创建一个列表，其中包含要覆盖的州
states_needed = set(['mt', 'wa', 'or', 'id', 'nv', 'ut', 'ca', 'az'])
# 创建广播台清单
stations = {}
stations['kone'] = set(['id', 'nv', 'ut'])
stations['ktwo'] = set(['wa', 'id', 'mt'])
stations['kthree'] = set(['or', 'nv', 'ca'])
stations['kfour'] = set(['nv', 'ut'])
stations['kfive'] = set(['ca', 'az'])
# 创建一个集合来存储最终选择的广播台
final_stations = set()

if __name__ == '__main__':
    while states_needed :
        best_station = None
        states_covered = set()
        for station,states in stations.items():
            covered = states_needed & states
            if len(covered) > len(states_covered):
                states_covered=covered
                best_station=station
        states_needed-=states_covered
        final_stations.add(best_station)

    print(final_stations)




